package salesforce.sortanarray;

import java.util.Arrays;
//只能向后
//https://leetcode.com/discuss/interview-question/789524/determine-minimum-numbers-of-moves-required-to-sort-the-array-in-ascending-order
public class SortAnArray2 {
    public static int minMove(int[] arr) {
        int[] sorted = new int[arr.length];
        System.arraycopy(arr, 0, sorted, 0, arr.length);
        Arrays.sort(sorted);

        int res = arr.length;
        for (int i = 0, j = 0; i < arr.length; i++) {
            if (arr[i] == sorted[j]) {
                j++;
                res--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,4,3,2,1};
        System.out.println(minMove(arr));
        arr = new int[]{5,1,3,2,};
        System.out.println(minMove(arr));
    }

}
